|
In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions. The axioms were first defined by Manuel Blum in 1967. Importantly, the Speedup and Gap theorems hold for any complexity measure satisfying these axioms. The most well-known measures satisfying these axioms are those of time (i.e., running time) and space (i.e., memory usage). == Definitions == A Blum complexity measure is a tuple with a Gödel numbering of the partial computable functions and a computable function : which satisfies the following Blum axioms. We write for the ''i''-th partial computable function under the Gödel numbering , and for the partial computable function . * the domains of and are identical. * the set is recursive. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Blum axioms」の詳細全文を読む スポンサード リンク
|